package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode647 {
    public int countSubstrings(String s) {
        int n = s.length();
        //1.创建dp数组,dp[i][j]表示子串s[i][j]是否是回文串
        boolean[][] dp = new boolean[n][n];
        //i==j,dp[i][j]=true,因为一个字符和自己必然构成回文
        //j==i+1表示两个紧邻的字符，如果一样则代表一样
        //j>i+1,首先判断s[i]==s[j],在相等的前提下看子问题s[i+1,j-1]是否回文
        int count = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <=j; i++) {
                if (i == j) {
                    dp[i][j] = true;
                    count++;
                } else if (j == i + 1 && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    count++;
                } else if (j > i + 1 && s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
    return count;
    }
}
